package leetcode.medium;

import org.junit.Test;

import java.util.Date;

/**
 * Created by hasee on 2017/5/26.
 */
public class OptimalDivision_553 {

    @Test
    public void test(){
        long time = 1499464800000L;
        System.out.println(new Date(time));
    }


    class Result {
        String str;
        double val;
    }

    public String optimalDivision(int[] nums) {
        int len = nums.length;
        return getMax(nums, 0, len - 1).str;
    }

    private Result getMax(int[] nums, int start, int end) {
        Result r = new Result();
        r.val = -1.0;

        if (start == end) {
            r.str = nums[start] + "";
            r.val = (double)nums[start];
        }
        else if (start + 1 == end) {
            r.str = nums[start] + "/" + nums[end];
            r.val = (double)nums[start] / (double)nums[end];
        }
        else {
            for (int i = start; i < end; i++) {
                Result r1 = getMax(nums, start, i);
                Result r2 = getMin(nums, i + 1, end);
                if (r1.val / r2.val > r.val) {
                    r.str = r1.str + "/" + (end - i >= 2 ? "(" + r2.str + ")" : r2.str);
                    r.val = r1.val / r2.val;
                }
            }
        }

        return r;
    }

    private Result getMin(int[] nums, int start, int end) {
        Result r = new Result();
        r.val = Double.MAX_VALUE;

        if (start == end) {
            r.str = nums[start] + "";
            r.val = (double)nums[start];
        }
        else if (start + 1 == end) {
            r.str = nums[start] + "/" + nums[end];
            r.val = (double)nums[start] / (double)nums[end];
        }
        else {
            for (int i = start; i < end; i++) {
                Result r1 = getMin(nums, start, i);
                Result r2 = getMax(nums, i + 1, end);
                if (r1.val / r2.val < r.val) {
                    r.str = r1.str + "/" + (end - i >= 2 ? "(" + r2.str + ")" : r2.str);
                    r.val = r1.val / r2.val;
                }
            }
        }

        return r;
    }
}
